package org.algorithm.biubiu.wheel_1.BFS算法;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

 重点就两句话： 1、两个数组之差的总和必须大于等于0，否则不能完成绕行
 2、 一个站的收益如果小于0，肯定不能作为起点；而连续的多个站也可以等效地看做一个站，如果其累积收益小于0，就跳过，寻找下一个


 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/open-the-lock
 */
public class $5月13日$打开转盘锁 {


    /**
     *
     */
    public int openLock(String[] deadends, String target) {
        Set<String> dead =  new HashSet();
        for(String v : deadends) dead.add(v);
        Set<String> visit = new HashSet();
        Queue<String> queue = new LinkedList();
        queue.add("0000");
        int res = 0;
        while(!queue.isEmpty()){
            int sz = queue.size();
            for(int i=0;i<sz;i++){
                String node = queue.poll();
                if(dead.contains(node)) continue;
                if(target.equals(node)) return res;
                for(int j=0;j<4;j++){
                    String downValue = down(node,j);
                    if(!visit.contains(downValue)){
                        visit.add(downValue);
                        queue.add(downValue);
                    }
                    String upValue = up(node,j);
                    if(!visit.contains(upValue)){
                        visit.add(upValue);
                        queue.add(upValue);

                    }
                }
            }
            res++;
        }
        return -1;

    }




    public String down(String s,int num){
        char[] ch = s.toCharArray();
        if(ch[num]=='0'){
            ch[num]='9';
        }else{
            ch[num]-=1;
        }
        return new String(ch);
    }


    public String up(String s,int num){
        char[] ch = s.toCharArray();
        if(ch[num]=='9'){
            ch[num]='0';
        }else{
            ch[num]+=1;
        }
        return new String(ch);
    }
}
